package mo.leetcode_top;

import mo.common.TreeNode;

public class LI0412 {

    private int count = 0;

    public int pathSum(TreeNode root, int sum) {
        int depth = depth(root);
        int[] path = new int[depth];
        findSum(root, sum, path, 0);
        return count;
    }


    private void findSum(TreeNode node, int sum, int[] path, int level) {
        if (node == null) {
            return;
        }
        path[level] = node.val;
        int t = 0;
        for (int i = level; i >= 0; i--) {
            t += path[i];
            if (t == sum) {
                count++;
            }
        }

        findSum(node.left, sum, path, level+1);
        findSum(node.right, sum, path, level+1);

        path[level] = Integer.MIN_VALUE;
    }

    private int depth(TreeNode node) {
       if (node == null) {
           return 0;
       }
       return 1 + Math.max(depth(node.left), depth(node.right));
    }

}
